package LeetCode;

import Util.ListNode;

/**
 * @author attcat
 * ---做一个有趣的程序员
 * @date 2022-10-17 21:12
 * @description
 */
public class LeetCode_21 {
    public static void main(String[] args) {
        LeetCode_21 leetCode21=new LeetCode_21();
        ListNode l1=new ListNode(1,new ListNode(2,new ListNode(4)));
        ListNode l2=new ListNode(1,new ListNode(3,new ListNode(4)));
//        ListNode p= leetCode21.mergeTwolists(l1,l2);
        ListNode d=leetCode21.mergeTwolists2( l1,  l2);
//        System.out.println(p);
        System.out.println(d);

    }
    /***
     * 循环+双指针
     */
    public ListNode mergeTwolists(ListNode l1, ListNode l2){
        if(l1 ==null){
           return  l2;
        }
        if(l2==null){
            return  l1;
        }
        ListNode resultNode=new ListNode(0);
        ListNode p=resultNode;
        while (l1 !=null && l2!=null){
            if(l1.val< l2.val){
                p.next=l1;
                l1=l1.next;
            }else {
                p.next=l2;
                l2=l2. next;
            }
            p=p.next;
        }
        if(l1!=null){
            p.next=l1;

        }
        if(l2!=null){
            p.next=l2;
        }

        return resultNode.next;

    }


    /****
     * 递归解决
     */
    public ListNode mergeTwolists2(ListNode l1, ListNode l2){
        if(l1 ==null){
            return  l2;
        }
        if(l2==null){
            return  l1;
        }
        if(l1.val< l2.val){
           l1.next= mergeTwolists2(l1.next,l2);
           return l1;
        }
        l2.next=mergeTwolists2(l1,l2.next);
        return l2;

    }

}
